package com.lw.leetcode.binary.c;

import com.lw.test.util.Utils;

/**
 * Created with IntelliJ IDEA.
 * 2141. 同时运行 N 台电脑的最长时间
 *
 * @author liw
 * @version 1.0
 * @date 2022/11/25 16:55
 */
public class MaxRunTime {

    public static void main(String[] args) {
        MaxRunTime test = new MaxRunTime();

        // 4
//        int n = 2;
//        int[] battries = {10,1};

        // 4
//        int n = 2;
//        int[] battries = {3, 3, 3};

        // 8
//        int n = 3;
//        int[] battries = {7,6,5,3,3,2};

        // 2
//        int n = 2;
//        int[] battries = {1, 1, 1, 1};

        // 95
//        int n = 5;
//        int[] battries = {47, 6, 97, 94, 33, 76, 22, 17, 80, 7};

        // 161
//        int n = 5;
//        int[] battries = {97, 22, 3, 31, 31, 82, 39, 50, 83, 40, 62, 35, 6, 61, 92, 14, 29, 4, 21, 3};

        //
        int n = 5;
        System.out.println(n);
        int[] battries = Utils.getArr(100000, 1, 1000000000, "c:\\lw\\aa.txt");

        long l = test.maxRunTime(n, battries);
        System.out.println(l);

    }

    public long maxRunTime(int n, int[] batteries) {
        long sum = 0;
        int st = Integer.MAX_VALUE;
        int end = 0;
        for (int t : batteries) {
            st = Math.min(st, t);
            end = Math.max(end, t);
            sum += t;
        }
        if (sum / n >= end) {
            return sum / n;
        }
        while (st < end) {
            int m = st + ((end - st + 1) >> 1);
            sum = 0;
            for (int t : batteries) {
                sum += (t <= m ? t : m);
            }
            if (sum / n >= m) {
                st = m;
            } else {
                end = m - 1;
            }
        }
        return sum / n;
    }


}
